package JZOffer; /**
 * 剑指 Offer 06. 从尾到头打印链表
 * 输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
 * **/

import java.util.Stack;

/**
  Definition for singly-linked list.
 **/
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

//方案一
class Solution06_1 {
    public int[] reversePrint(ListNode head) {
        if (head == null) return new int[]{};

        //计算链表的长度
        int length = 0;
        ListNode curr = head;
        while (curr != null){
            length++;
            curr = curr.next;
        }

        // 初始化存放结果的数组
        int[] res = new int[length];

        //按照反方向将链表节点值存放在数组中
        int i = length - 1;
        curr = head;
        while (curr != null){
            res[i] = curr.val;
            i--;
            curr = curr.next;
        }
        return res;
    }
}

//方案二 辅助栈
class Solution06_2 {
    public int[] reversePrint(ListNode head) {
        if (head == null) return new int[]{};

        //先将链表从头至尾的节点依次添加到栈中
        Stack<ListNode> stack = new Stack<>();
        ListNode curr = head;
        while (curr != null){
            stack.push(curr);
            curr = curr.next;
        }

        //依次从栈中取出节点，然后添加到数组中
        int[] res = new int[stack.size()];
        int i = 0;
        while (!stack.isEmpty()){
            res[i] = stack.pop().val;
            i++;
        }
        return res;
    }
}
